package com.yize.leetcode;

import java.util.Stack;

/**
 * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 *
 * 注意:
 *
 * num 的长度小于 10002 且 ≥ k。
 * num 不会包含任何前导零。
 * 示例 1 :
 *
 * 输入: num = "1432219", k = 3
 * 输出: "1219"
 * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
 * 示例 2 :
 *
 * 输入: num = "10200", k = 1
 * 输出: "200"
 * 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 * 示例 3 :
 *
 * 输入: num = "10", k = 2
 * 输出: "0"
 * 解释: 从原数字移除所有的数字，剩余为空就是0。
 * https://leetcode-cn.com/problems/remove-k-digits/
 */
public class RemoveKDigits {
    public String removeKDigits(String num, int k) {
        if(num==null||num.length()<=k){
            return null;
        }
        Stack<Character> stack=new Stack<>();
        char[] cs=num.toCharArray();
        for (int i=0;i<cs.length;i++){
            while (k>0&&!stack.isEmpty()&&stack.peek()>cs[i]){
                stack.pop();
                k--;
            }
            stack.push(cs[i]);
        }
        while (k-->0){
            stack.pop();
        }
        Stack<Character> nStack=new Stack<>();
        while (!stack.isEmpty()){
            nStack.push(stack.pop());
        }
        while (!nStack.isEmpty()&&nStack.peek()=='0'){
            nStack.pop();
        }
        StringBuilder sb=new StringBuilder();
        while (nStack.isEmpty()==false){
            sb.append(nStack.pop());
        }
        if(sb.length()==0){
            sb.append(0);
        }

        return sb.toString();
    }
}
